\documentclass[12pt, titlepage]{article}

\usepackage[UTF8]{ctex}
\usepackage{url}
\usepackage[hidelinks]{hyperref}
\usepackage{listings}
\usepackage{booktabs, siunitx}
\usepackage{bm}
\usepackage{graphicx}
\usepackage{fancyhdr}
\usepackage{amsmath}


\author{eleve11}
\title{凸函数、凹函数}
\pagestyle{fancy}

\begin{document}
\maketitle

\section{介绍}
通常在实践中，要最小化的函数具有几个极值点，因此，由优化算法定位的极值点是否是全局点的不确定性产生。在称为凸函数或凹函数的特定类函数中，任何局部极值点也是全局极值点。因此，如果目标函数是凸的或凹的，则可以确保最优性。 \\

\newtheorem{thm}{定义}
\begin{thm}
    一个集合$\Re \subset E_n$($E_n$为n维的欧式空间)中的每一对点$(x_1, x_2) \subset \Re$，并且对于每一个实数$\alpha(0 < \alpha < 1)$，有$x = \alpha x_1 + (1-\alpha)x_2$也属于集合$\Re$，则说集合$\Re$是凸的，否则是非凸的。
\end{thm}

一个定义在凸集$\Re$的函数$f(x)$是\textbf{凸函数}，对于每一对$(x_1, x_2)\in \Re$以及任意实数$\alpha$，以下不等式成立:
\begin{displaymath}
  f[\alpha x_1 + (1-\alpha)x_2] \leq \alpha f(x_1) + (1-\alpha)f(x_2)
\end{displaymath}
如果$x_1 \neq x_2$，则有
\begin{displaymath}
  f[\alpha x_1 + (1-\alpha)x_2] < \alpha f(x_1) + (1-\alpha)f(x_2)
\end{displaymath}
满足上式的函数$f(x)$为\textbf{严格凸函数}。 \\
\indent 如果函数$\phi (x)$是定义在凸集$\Re$的函数，并且$f(x) = - \phi (x)$是凸函数，则函数$\phi (x)$为\textbf{凹函数}，如果函数$f(x)$为严格凸函数，则$\phi (x)$为严格凹函数。\\

\newtheorem{law}{定理}
\begin{law} \label{citelaw}
  $a>0,b>0$，$f_1 (x),f_2 (x)$为定义在凸集$\Re$上的凸函数，则两个函数的线性组合：$f(x)=a f_1(x) + b f_2(x)$在凸集$\Re$上也是凸函数。
\end{law}
\textbf{证明如下}： \\
已知$a, b > 0$，且$f_1 (x), f_2 (x)$为凸函数 \\
由凸函数定义可知，对于任意对$(x_1, x_2) \in \Re$，$x=\alpha x_1 + (1-\alpha )x_2$\\
$f_1 (x) = f_1 [\alpha x_1 + (1-\alpha)x_2] \leq \alpha f_1(x_1) + (1-\alpha )f_1(x_2)$ \\
$f_2 (x) = f_2 [\alpha x_1 + (1-\alpha)x_2] \leq \alpha f_2(x_1) + (1-\alpha )f_2(x_2)$ \\
则函数$f(x) = a f_1(x) + b f_2(x)$有: \\
$f(x) = a f_1 [\alpha x_1 + (1-\alpha)x_2] + bf_2 [\alpha x_1 + (1-\alpha)x_2] \leq \alpha [a f_1(x_1) + b f_2(x_1)] + (1-\alpha )[a f_1(x_2) + b f_2(x_2)]$ \\
也即线性组合函数：$f(x) \leq \alpha f(x_1) + (1 - \alpha) f(x_2)$，得证。\\
\indent 在一篇论文上看到过几个凸函数简单的加在一起，有了这个性质，我们便轻易可知得到的组合函数依旧是一个凸函数，依旧继承凸函数的良好特性。\\
\indent 凸函数与凸集的关系如下定理\ref{law}
\begin{law} \label{law}
  如果函数$f(x)$为凸集$\Re$上的凸函数，则集合$S_c = \{x: x \in \Re, \quad f(x) \leq K \}$也是凸集，其中$K$为任意实数。
\end{law}
\indent 依旧可以使用凸函数的性质来证明，通过这个定理我们也就知道凸函数的性质之好了，在缩小凸函数的定义域范围时，我们依旧可以得到一个性质良好的局部凸函数。\\
\indent 凸函数与梯度、Hessian有关的性质:
\begin{law}
  如果函数$f(x)$有一阶偏导数，定义在凸集$\Re$上，$g(x)$为函数$f(x)$的梯度，对于所有$x$以及$x_1 \in \Re$，有且只有：$f(x_1) \geq f(x) + g(x)^T (x_1 -x)$，则$f(x)$在$\Re$上说是凸的。
\end{law}
\begin{law}
  当且仅当$f(x)$的Hessian矩阵是半正定，$f(x)\in C^2$的在凸集$\Re$上是凸的。
\end{law}

\section{凸函数的优化}
\begin{law}
  凸函数中局部最小值与全局最小值的关系 \\
  如果函数$f(x)$是一个定义在凸集$\Re$上的凸函数，则有: \\
  (a). 凸函数$f(x)$最小值形成的点集合$S_c$是凸的。\\
  (b). 凸函数$f(x)$的局部最小值都是全局最小值
\end{law}
\begin{law}
  如果函数$f(x)\in C^1$是一个定义在凸集$\Re$上的凸函数，存在一个点$x^*$对于所有$x_1 \in \Re$有$g(x^*)^T d \geq 0$($d = x_1 - x^*$)，则说$x^*$是函数$f(x)$一个全局最小值
\end{law}
\begin{law}
  凸函数的最大值的位置 \\
  如果$f(x)$是一个定义在有边界，封闭的凸集$\Re$上的凸函数，则函数$f(x)$的最大值则会在凸集$\Re$的边界上取到。
\end{law}

\section{习题栗子}
\noindent 下列均是引用书籍中的练习题。未有解析，又是自学，也未能找到志同道合之人讨论学习，在此给出的都是本人的思路。 \\
\noindent 1. 两个定义在凸集$\Re$上的凸函数，证明$f(x)=a f_1 (x) + b f_2(x)$在$\Re$上式凸函数，其中$a$和$b$是非负标量。\\
由定理\ref{citelaw}可知。两个凸函数的线性组合需要在系数都为正数是成立，这题考虑的便是这个，当然此处我也只是给出我的思考，能力有限，未能给出证明。\\
当$a,b$皆小于零时，这是一个凹函数了，当$a,b$其中一个小于0 \\
$f(x) = a f_1 [\alpha x_1 + (1-\alpha)x_2] + bf_2 [\alpha x_1 + (1-\alpha)x_2] \overset{?}{\leq} \alpha [a f_1(x_1) + b f_2(x_1)] + (1-\alpha )[a f_1(x_2) + b f_2(x_2)]$这个不等式的确定性就无法得出了，也就无法保证$f(x)$是凸函数了。
\\ \\
\noindent 2. 假设函数$f_1 (x)$和$f_2 (x)$均为凸函数，令$f(x) = \max \{ f_1 (x) , f_2 (x) \}$，证明函数$f(x)$也为为凸函数。\\
\noindent $f(x) = \max \{ f_1 (x), f_2 (x) \}$，也就是$f(x) = \{ 0, 1 \}f_1 (x) + \{ 0, 1 \}f_2 (x)$的线性组合 \\
\noindent 由定理\ref{law}，可知，凸函数在局部依旧继承者凸函数的良好性质。max操作，也就是讲两个函数切分成多个局部。

\newpage
\begin{thebibliography}{99}
  \bibitem{b} Andreas A, Wu-Sheng L. Practical Optimization Algorithms and Engineering Applications (2007)
\end{thebibliography}

\end{document}
